package com.shuo.dsa.leetcode;

/**
 * Created by shuoGG on 2018/10/14 0014
 */
public class GasStation {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        /* 1.先排除掉油总体就已经不够用的情况 */
        int[] rest = new int[gas.length];
        int res = 0;
        for (int i = 0; i < gas.length; i++) {
            rest[i] = gas[i] - cost[i];
            res += rest[i];
        }
        if (res < 0)
            return -1;
        /* 2.普通情况 */
        int len = rest.length;
        for (int i = 0; i < rest.length; i++) {
            int start = (i + 1) % len;
            int end = i;
            int total = rest[i];
            if (total < 0)
                continue;
            while (start != end) {
                total += rest[start];
                if (total < 0)
                    break;
                start = (start + 1) % len;
            }
            if (total >= 0)
                return i;
        }
        return -1;
    }
}
